#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (head == nullptr || head->next == nullptr)
        {
            return head;
        }
        if (left == right)
        {
            return head;
        }
        ListNode *h = new ListNode();
        h->next = head;
        // 添加一个头节点
        ListNode * pre = h, *p = pre->next, *q;
        int j = 0;
        // 左边的指针指向的是left位置节点的前驱节点
        while (j < left - 1 && p != nullptr)
        {
            j++;
            // 找到了p节点的前驱节点
            pre = p;
            p = p->next;
        }
        // 将left + 1 ～ right的节点插入到pre之后
            while (j < right - 1 && p != nullptr)
            {
                q = p->next;
                // 删除节点q
                p->next = q->next;
                // 将节点q插入到pre之后
                q->next = pre->next;
                pre->next = q;
                j++;
            }
            return h->next;   
    }
};

int main()
{

    return 0;
}